BOJ_11053_가장 긴 증가하는 부분 수열

LIS(Longest Increasing Subsequence) 알고리즘을 사용해서 푸는 문제

LIS의 전형적인 문제이다

N = int(input())  
nums = list(map(int, input().split()))  
dp = [1] * (N + 1)  
  
for i in range(1, N):  
    num = nums[i]  
  
    for j in range(0, i):  
        if nums[j] < num:  
            dp[i] = max(dp[i], dp[j] + 1)  
  
print(max(dp))